package leetcode;

/**
 * 509. 斐波那契数
 */
public class Solution509 {
//    public int fib(int n) {
//        if(n==0){
//            return 0;
//        }
//        if(n==1){
//            return 1;
//        }
//        return fib(n-1) + fib(n-2);
//    }
//    int[] temp = null;
//    public int fib(int n) {
//        temp = new int[n+1];
//        return fib2(n);
//    }
//    public int fib2(int n) {
//        if(n==0||n==1) return n;
//        if(temp[n] == 0){
//            temp[n] = fib2(n-1) + fib2(n-2);
//        }
//        return temp[n];
//    }

    public int fib(int n) {
        if(n==0 || n==1) return n;
        int[] temp = new int[n+1];
        temp[0]=0;
        temp[1]=1;
        for (int i = 2; i <= n; i++) {
            temp[i] = temp[i-1]+temp[i-2];
        }
        return temp[n];
    }


}
